Regularized decomposition methods for deterministic and stochastic convex optimization and application to portfolio selection with direct transaction and market impact costs

摘要

We define a regularized variant of the Dual Dynamic Programming algorithmcalled REDDP (REgularized Dual Dynamic Programming) to solve nonlinear dynamicprogramming equations. We extend the algorithm to solve nonlinear stochasticdynamic programming equations. The corresponding algorithm, called SDDP-REG,can be seen as an extension of a regularization of the Stochastic Dual DynamicProgramming (SDDP) algorithm recently introduced which was studied for linearproblems only and with less general prox-centers. We show the convergence ofREDDP and SDDP-REG. We assess the performance of REDDP and SDDP-REG onportfolio models with direct transaction and market impact costs. Inparticular, we propose a risk-neutral portfolio selection model which can becast as a multistage stochastic second-order cone program. The formulation ismotivated by the impact of market impact costs on large portfolio rebalancingoperations. Numerical simulations show that REDDP is much quicker than DDP onall problem instances considered (up to 184 times quicker than DDP) and thatSDDP-REG is quicker on the instances of portfolio selection problems withmarket impact costs tested and much faster on the instance of risk-neutralmultistage stochastic linear program implemented (8.2 times faster).